#include<bits/stdc++.h>
#include "graph.h"
using namespace std;
#define A Answer
#define M Move
#define D NumberOfRoads()
#define L LastRoad()
#define C Color()
const int N=205;
struct node{
	int id,l,r;
};
int n=1,cnt[N],dis[N][N];
vector <node> e[N];
vector <int> s[N],es[N];
int fa[N],efa[N];
int col[10][N];
inline void add(int x,int y){
	dis[x][y]=dis[y][x]=1;
}
inline void addedge(int x,int y){
	e[x].push_back({y,1,n});
}
inline void calc(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j||j==k||k==i) continue;
				dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		} 
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(dis[i][j]>n) continue;
			cnt[dis[i][j]]++;
		}
	}
}
void dfs(int x,int f){
	fa[x]=f;efa[x]=L;
	add(f,x);
	for(int i=1;i<=D;i++){
		if(i==L) continue;
		M(i,2);
		if(C==2){
			M(L,2);
			addedge(x,i);
			continue;
		}
		s[x].push_back(++n),es[x].push_back(i);
		dfs(x,n);
	}
	M(efa[x],2);
}
int deep=0;
void build(int dep,int l,int r){
	deep=dep;
	if(l==r) return ;
	int mid=(l+r)>>1;
	if((r-l+1)%2){
		for(int i=l;i<=mid-1;i++) col[dep][i]=1;
		col[dep][mid]=2;
		for(int i=mid+1;i<=r;i++) col[dep][i]=3;
		build(dep+1,l,mid-1),build(dep+1,mid+1,r);
	}
	else{
		for(int i=l;i<=mid;i++) col[dep][i]=1;
		for(int i=mid+1;i<=r;i++) col[dep][i]=3;
		build(dep+1,l,mid),build(dep+1,mid+1,r);
	}
}
void cover(int x,int dep){
	for(int i=0;i<(int)s[x].size();i++){
		M(es[x][i],col[dep][x]);
		cover(s[x][i],dep);
		M(L,col[dep][s[x][i]]);
	}
}
void find(int x,int dep){
	for(auto i:e[x]){
		if(i.l==i.r) continue;
		M(x,i.id);
		int mid=(i.l+i.r)>>1;
		if(C==1){
			if((i.r-i.l+1)%2) i.r=mid-1;
			else i.r=mid;
		}
		else if(C==2) i.l=i.r=mid;
		else i.l=mid+1;
		M(L,C);
	}
	for(int i=0;i<(int)s[x].size();i++){
		M(es[x][i],col[dep][x]);
		find(s[x][i],dep);
		M(L,col[dep][s[x][i]]);
	}
}
inline void solve(){
	for(int i=1;1<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=0x3f3f3f3f;
		}
	}
	dfs(1,0);
	build(1,1,n);
	for(int i=1;i<=deep;i++){
		cover(1,i);
		find(1,i);
	}
	for(int i=1;i<=n;i++){
		for(auto j:e[i]){
			add(i,j.l);
		}
	}
	calc();
}
void Inspect(int R) {
    solve();
    for(int i=1;i<=R;i++) A(i,cnt[i]);
}
